package algorithm.middle;

import java.util.*;
import java.util.stream.Collectors;

/**
 * 你要开发一座金矿，地质勘测学家已经探明了这座金矿中的资源分布，并用大小为 m * n 的网格 grid 进行了标注。每个单元格中的整数就表示这一单元格中的黄金数量；如果该单元格是空的，那么就是 0。
 * <p>
 * 为了使收益最大化，矿工需要按以下规则来开采黄金：
 * <p>
 * 每当矿工进入一个单元，就会收集该单元格中的所有黄金。
 * 矿工每次可以从当前位置向上下左右四个方向走。
 * 每个单元格只能被开采（进入）一次。
 * 不得开采（进入）黄金数目为 0 的单元格。
 * 矿工可以从网格中 任意一个 有黄金的单元格出发或者是停止。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/path-with-maximum-gold
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class GetMaximumGold1219 {
    //DFS 回溯
    public int getMaximumGold(int[][] grid) {
        int num = 0;
        for (int i=0;i<grid.length;i++){
            for (int j=0;j<grid[0].length;j++){
                num = Math.max(num,dfs(grid,i,j));
            }
        }
        return num;
    }

    public int dfs(int[][] grid, int x, int y) {
        int cur = grid[x][y];
        grid[x][y] = 0;
        int res = 0;
        if (x-1>=0 && grid[x-1][y]!=0){
            //上
            res = dfs(grid,x-1,y);
        }
        if(x+1<grid.length && grid[x+1][y]!=0){
            //下
            res = Math.max(res,dfs(grid,x+1,y));
        }
        if (y-1>=0 && grid[x][y-1]!=0){
            //左
            res = Math.max(res,dfs(grid,x,y-1));
        }
        if(y+1<grid[0].length && grid[x][y+1]!=0){
            //右
            res = Math.max(res,dfs(grid,x,y+1));
        }
        grid[x][y] = cur;
        res = res +cur;
        return  res;
    }
}
